package com.zhou.xin.test.algorithm;

import java.util.Scanner;

/**
 * @author ZhouXin
 * @ClassName SearchAlgorithm
 * @description: 排序算法
 * @date 2023年12月12日
 * @version: 1.0
 */
public class SortAlgorithm {

    /**
     * 冒泡排序
     * @param arr 排序数组
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换arr[j]和arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 插入排序
     * @param arr 排序数组
     */
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    /**
     * @description 希尔排序
     * @param arr 排序数据
     * @return void
     * @date 2024/1/11 15:20
     **/
    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while (gap > 1) {
            gap = gap / 2;
            for (int i = 0; i < arr.length - gap; i++) {
                int end = i;
                int tep = arr[end + gap];
                while (end >= 0) {
                    if (tep < arr[end]) {
                        arr[end + gap] = arr[end];
                        end -= gap;
                    } else {
                        break;
                    }
                }
                arr[end + gap] = tep;
            }
        }
    }

    /**
     * @description 选择排序
     * @param arr 排序数组
     * @return void
     * @date 2024/1/11 19:40
     **/
    public static void selectSort(int[] arr) {
        //保存参与单趟排序的第一个数和最后一个数的下标
        int begin = 0, end = arr.length - 1;
        while (begin < end) {
            //保存最大值的下标
            int max = begin;
            //保存最小值的下标
            int min = begin;
            //找出最大值和最小值的下标
            for (int i = begin; i <= end; ++i) {
                if (arr[i] < arr[min]) {
                    min = i;
                }
                if (arr[i] > arr[max]) {
                    max = i;
                }
            }
            //最小值放在序列开头
            int tem = arr[min];
            arr[min] = arr[begin];
            arr[begin] = tem;
            //防止最大的数在begin位置被换走
            if (begin == max) {
                max = min;
            }
            //最大值放在序列结尾
            int tep = arr[max];
            arr[max] = arr[end];
            arr[end] = tep;
            ++begin;
            --end;
        }
    }



    /**
     * @description
     * @param args 数组参数
     * @return void
     * @date 2023/12/12 15:05
     **/
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        Scanner inputNum = new Scanner(System.in);
        System.out.println("请输入数据的数量(按Enter后继续)：");
        int[] arr = new int[inputNum.nextInt()];
        System.out.println("请输入排序的整数(按Enter后继续)：");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = input.nextInt();
        }
        selectSort(arr);
        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
